package SubjectHashTable;

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

public class Intersection {
	
/**
 * 难度：简单
 * 
 * 349. 两个数组的交集
 * 	给定两个数组，编写一个函数来计算它们的交集。
 * 
 * 示例 1：
 * 	输入：nums1 = [1,2,2,1], nums2 = [2,2]
 * 	输出：[2]
 * 
 * 示例 2：
 * 	输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
 * 	输出：[9,4]
 * 
 * 说明：
 * 	输出结果中的每个元素一定是唯一的。
 * 	我们可以不考虑输出结果的顺序。
 *
 * */	

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Intersection i = new Intersection();
		int[] a = i.intersection2(new int[] {4,9,9,5}, new int[] {9,9,8,4});
		for(int j=0;j<a.length;j++) {
			System.out.print(a[j]+",");
		}
	}
	//自己写
	public int[] intersection(int[] nums1, int[] nums2) {
		//把数组1转换成list
		List<Integer> list = Arrays.stream(nums1).boxed().collect(Collectors.toList());
		//set保存两数组交集
		Set<Integer> set = new HashSet<>();
		for(int i:nums2) {
			if(list.contains(i)) {
				set.add(i);
			}
		}
		//把set转换成数组输出
		int[] i = set.stream().mapToInt(Integer::valueOf).toArray();
		return i;
    }
	//方法一：两个集合
	public int[] intersection1(int[] nums1, int[] nums2) {
		Set<Integer> set1 = new HashSet<>();
		Set<Integer> set2 = new HashSet<>();
		for(int i:nums1) {
			set1.add(i);
		}
		for(int i:nums2) {
			set2.add(i);
		}
		Set<Integer> intersectionSet = new HashSet<>();
		if(set1.size()>set2.size()) {
			for(int i:set1) {
				if(set2.contains(i)) {
					intersectionSet.add(i);
				}
			}
		}else {
			for(int i:set2) {
				if(set1.contains(i)) {
					intersectionSet.add(i);
				}
			}
		}
		int[] res = new int[intersectionSet.size()];
		int index=0;
		for(int num:intersectionSet) {
			res[index++]=num;
		}
		return res;
    }
	//方法二：排序 + 双指针
	public int[] intersection2(int[] nums1, int[] nums2) {
		Arrays.sort(nums1);
		Arrays.sort(nums2);
		int length1=nums1.length,length2=nums2.length;
		int index=0,index1=0,index2=0;
		int[] intersection = new int[length1+length2];
		while(index1<length1&&index2<length2) {
			int num1=nums1[index1];
			int num2=nums2[index2];
			if(num1==num2) {
				// 保证加入元素的唯一性
				if(index==0||num1!=intersection[index-1]) {
					intersection[index++]=num1;
				}
				index1++;
				index2++;
			}else if(num1<num2){
				index1++;
			}else {
				index2++;
			}
		}
		return intersection;
	}
}
